﻿#pragma once
#include <assert.h>
#include <iostream>
#include <vector>
#include <time.h>
#include <algorithm>
#include <windows.h>
#include <unordered_map>

#include <thread>
#include <mutex>
using std::cout;
using std::endl;

// 小于等于MAX_BYTES，就找thread cache申请
// 大于MAX_BYTES，就直接找page cache或者系统堆申请
static const size_t MAX_BYTES = 256 * 1024;
// thread cache 和 central cache自由链表哈希桶的表大小
static const size_t NFREE_LIST = 208;
// page cache 管理span list哈希表大小
static const size_t NPAGES = 128;
// 页大小转换偏移, 即一页定义为2^13,也就是8KB
static const size_t PAGE_SHIFT = 13;

#ifdef _WIN32
typedef size_t PAGE_ID;
#elif _WIN64
typedef unsigned long long PAGE_ID;

#endif 

inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage * (1 << 12), MEM_COMMIT | MEM_RESERVE,
		PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}




//取头上4/8个字节
static void*& NextObj(void* obj)         //1
{
	return *(void**)obj;      //*（void**）得到前四个字节或者是前8个字节作为下一个节点地址的空间
	//就是用头四个字节或者8个字节用来存储地址，你将其取出，他就是地址
}
//管理切分好的小对象自由链表
class FreeList
{
public:
	void Push(void* obj)
	{
		// 头插
		assert(obj);
		//*(void**)obj = _freeList;
		NextObj(obj) = _freeList;
		_freeList = obj;

		++_size;
	}

	void PushRange(void* start, void* end, size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;

		_size += n;
	}

	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n >= _size);
		start = end = _freeList;
		for (size_t i = 0; i < n - 1; ++i)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		
		_size -= n;
	}

	void* Pop()
	{
		assert(_freeList);
		//头删
		//先保存下一个  返回第二个
		void* obj = _freeList;
		_freeList = NextObj(obj);

		--_size;

		return obj;
	}

	bool Empty()
	{
		return _freeList == nullptr;
	}

	size_t& MaxSize()
	{
		return _maxSize;
	}

	size_t Size()
	{
		return _size;
	}

private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;
	size_t _size = 0;
};

//计算对象大小的对其映射规则
class SizeClass
{
public:
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128]						8byte对齐      		freelist[0,16)
	// [128+1,1024]					16byte对齐  			freelist[16,72)
	// [1024+1,8*1024]				128byte对齐  		freelist[72,128)
	// [8*1024+1,64*1024]			1024byte对齐    		freelist[128,184)
	// [64*1024+1,256*1024]		8*1024byte对齐  		freelist[184,208)

	//size_t _RoundUp(size_t size, size_t alignNum)
	//{
	//	size_t alignSize;
	//	if (size % 8 != 0)
	//	{
	//		//普通人版本
	//		// 9-15 / 8 == 1   (1+1) * 8 = 16
	//		//17  / 8 = 2      2 / 8 = (2 + 1) * 16 = 24
	//		alignSize = (size / alignNum + 1) * alignNum;       //切记 
	//	}
	//	else                //==8不需要处理,8的倍数
	//	{
	//		alignSize = size;
	//	}
	//	return alignSize;
	//}


	//高手版本
	static inline size_t _RoundUp(size_t size, size_t alignNum)
	{
		//1-8
		//8+7 ==15    15&~7
		//00001111		15
		//00000111		7
		//11111000		~7
		//00001000		8
		return ((size + alignNum - 1) & ~(alignNum - 1));
	}

	static size_t RoundUp(size_t size)
	{
		if (size <= 128)    //8字节对齐
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)    //16字节对齐
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)    //128字节对齐
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)    //1024字节对齐
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)    //8*1024字节对齐
		{
			return _RoundUp(size, 8 * 1024);
		}
		else                            // 一般走不到这  以防万一
		{
			assert(false);
			return -1;
		}
	}



	//size_t _Index(size_t bytes,size_t alignNum)
	//{
	//	if (bytes % alignNum == 0)
	//	{
	//		return bytes / alignNum - 1;
	//	}
	//	else
	//	{
	//		return bytes / alignNum;
	//	}
	//}
	//////////没搞明白
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}

	// 计算映射的哪一个自由链表桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128) {
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024) {
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024) {
			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1]
				+ group_array[0];
		}
		else if (bytes <= 256 * 1024) {
			return _Index(bytes - 64 * 1024, 13) + group_array[3] +
				group_array[2] + group_array[1] + group_array[0];
		}
		else {
			assert(false);
		}
		return -1;
	}

	// 一次从中心缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		// [2, 512]，一次批量移动多少个对象的(慢启动)上限值
		// 小对象一次批量上限高
		// 小对象一次批量上限低
		int num = MAX_BYTES / size;        //MAX_BYTES  256kb
		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;
		return num;
	}

	// 计算一次向系统获取几个页
	// 单个对象 8byte
	// ...
	// 单个对象 256KB
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;
		npage >>= PAGE_SHIFT;
		if (npage == 0)
			npage = 1;
		return npage;
	}

};

//管理连续多个页的大块内存跨度
struct Span
{
	PAGE_ID _pageId = 0;  //大块内存的起始页的页号
	size_t _n = 0;		  //页的数量

	Span* _next = nullptr;		  //双向链表结构
	Span* _prev = nullptr;

	size_t _useCount = 0;  //切好的小块内存，被分配给thread Cache的计数
	void* _freeList = nullptr;   //切好的小块内存的自由链表

	bool _isUse = false;  //是否正在使用
};

//带头双向循环链表
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}

	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}

	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
	}

	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);

		Span* prev = pos->_prev;
		Span* next = pos->_next;
		prev->_next = next;
		next->_prev = prev;

		//free(pos);   //不需要Delete
	}
private:
	Span* _head;
public:
	std::mutex _mtx;  //桶锁
};





